#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <sstream>
#include <string>
#include <windows.h>
#include <ctime>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <process.h>
#include "LogWriter.h"

using namespace std;

long long totalCount; //number of chunks and total number of elements in input array
char *tempPath; //path for temp chunk files
long bufferSize; //size of buffer which we read from memory-mapped file
long long fileSize; //input file size
int tempBufferSize; //if chunking cuts some numbers this value is > 0
char *tempBuffer; //cutted number part
long long offset; //offset in input file
long long queueBufferLength; //number of elements in each queue
deque<long long> *positions; //positions of spaces in chunks (this is needed for getting elements from chunks and pushing them to queues)
long long *fileSizes; //sizes of chunks
long long *offsets; //offsets in chunks
char **fileNames; //file names of chunks
SYSTEM_INFO info; //system information
long granularity; //system granularity
MEMORYSTATUSEX status; //memory status
LogWriter::LogWriter logger;
int chunksNum; //number of chunks
char *inputFileName;
char *outputFileName;

enum except {INVALID_ARGS = 1, 
	READING_ERROR, 
	FORMAT_ERROR, 
	MAPPING_FAILED, 
	FAILED_OPENING_FILE, 
	TEMP_FILE_WRITING_FAILED,
	CREATING_TEMP_FILE_FAILED,
	CREATING_OUTPUT_FILE_FAILED, 
	WRITING_OUTPUT_FAILED,
	EMPTY_FILE_ERROR};

//qsort comparator
int compare (const void * a, const void * b)
{
	const unsigned int *x = (unsigned const int *)a, *y = (unsigned const int *)b;
	if(*x > *y)
		return 1;
	else
		return (*x < *y) ? -1 : 0;
}

//initializing base variables
void Initialize(int argc, char *argv[])
{
	char *logFileName = "log.txt";
	logger = LogWriter::LogWriter(logFileName);
	if (argc != 3)
	{
		logger.Fatal("Wrong command-line parameters");
		exit(0);
	}
	inputFileName = argv[1];
	outputFileName = argv[2];
	tempPath = "C:\\temp\\";
	CreateDirectory(tempPath, NULL);
	struct _stat64 stat_buf;
	int rc = _stat64(inputFileName, &stat_buf);
	if (rc == -1)
	{
		logger.Fatal("Error reading input file");
		exit(0);
	}
	fileSize = stat_buf.st_size; //getting input file size
	if (fileSize == 0)
	{
		logger.Fatal("Input file is empty");
		exit(0);
	}
	status.dwLength = sizeof(status);
	GlobalMemoryStatusEx(&status); //getting memory info
	tempBufferSize = 0;
	GetSystemInfo(&info);
	granularity = info.dwAllocationGranularity; //getting system granularity
	bufferSize = (status.ullAvailPhys * 0.7) / 5; //setting buffer size
	chunksNum = (fileSize / bufferSize) + 1;
	queueBufferLength = ((status.ullAvailPhys * 0.7) / chunksNum) / 40; //setting queue buffer length
	fileSizes = 0;
	fileNames = 0;
	offsets = 0;
	positions = 0;
	fileSizes = new long long[chunksNum];
	fileNames = new char*[chunksNum];
	offsets = new long long[chunksNum];
	positions = new deque<long long>[chunksNum];
}

void Deinitialize()
{
	free(fileSizes);
	free(fileNames);
	free(offsets);
}

//chunk processing function
void ProcessChunk(char *chunk, bool cutted, int inputSize, int index)
{
	logger.Debug("File with index %d started processing", index);

	if (chunk == NULL)
	{
		return;
	}

	long long num = 0;
	unsigned int *inputArray = new unsigned int[inputSize / 2];
	int space_pos = 0;
	deque<long long> tmp;

	int size = 0;
	int numSize = 0;

	//pushing elements to array
	for (int i = 0; i < inputSize; i++)
	{
		if (chunk[i] >= '0' && chunk[i] <= '9')
		{
			if (++numSize < 12)
			{
				num *= 10;
				num += chunk[i] - '0';
			}
			if (num >= 4294967296)
			{
				logger.Fatal("Invalid input");
				exit(0);
			}
		}
		else if (chunk[i] == ' ')
		{
			inputArray[size++] = num;
			num = 0;
			numSize = 0;
			space_pos = i;
		}
		else
		{
			logger.Fatal("Invalid input");
			exit(0);
		}
	}
	inputArray[size++] = num;

	//handling cutted numbers
	if (cutted)
	{
		size--;
		tempBufferSize = inputSize - space_pos - 1;
		tempBuffer = new char[tempBufferSize];
		int j = 0;
		for (int i = space_pos + 1; i < inputSize; i++)
		{
			tempBuffer[j] = chunk[i];
			j++;
		}
		inputSize -= tempBufferSize;
	}
	else
	{
		tempBufferSize = 0;
	}

	free(chunk);

	totalCount += size;

	//sorting array using standard qsort function
	qsort(inputArray, size, sizeof(unsigned int), compare);

	char *outputfn = new char;
	sprintf(outputfn, "%s%d", tempPath, index);

	fileSizes[index] = inputSize;
	fileNames[index] = outputfn;

	char *output =  new char[inputSize];

	long long position = 0;

	//writing sorted array to buffer and then to file
	HANDLE out = CreateFile(outputfn,
		GENERIC_WRITE, 
		FILE_SHARE_WRITE, 
		NULL, 
		CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL, 
		NULL);

	if (!out)
	{
		logger.Fatal("Creating temp file failed");
		exit(0);
	}

	for (int i = 0; i < size; i++)
	{
		char *temp = new char[10];
		sprintf(temp, "%u", inputArray[i]);
		int length = strlen(temp);
		for (int i = 0; i < length; i++)
		{
			output[position + i] = temp[i];
		}
		free(temp);
		position += length;
		if (i != size - 1)
		{
			output[position] = ' ';
			if (i % queueBufferLength == 0 && i != 0)
				tmp.push_front(position);
			position++;
		}
	}

	positions[index] = tmp;

	DWORD bytesWritten;
	bool written = WriteFile(out, output, inputSize, &bytesWritten, 0);
	if (!written)
	{
		logger.Fatal("Failed writing to temp file");
		exit(0);
	}
	CloseHandle(out);
	free(output);

	tmp.clear();

	free(inputArray);

	logger.Debug("File with index %d processed", index);
}

//function which splits input file into chunks
void Split(char *inputFileName)
{
	int index = 0;
	long long curPosition = 0;
	logger.Debug("Splitting started");
	
	OFSTRUCT tOfStr;
	tOfStr.cBytes = sizeof tOfStr;

	offset = 0;

	while (offset < fileSize)
	{
		long k = 0;
		bool cutted = false;

		if (fileSize - offset <= bufferSize)
		{
			bufferSize = fileSize - offset;
		}

		//setting offset in file according to system granularity
		long long tempOffset = (offset / granularity) * granularity;

		//getting low offset word and high offset word
		long long offsetHigh = ((tempOffset >> 32) & 0xFFFFFFFF);
		long long offsetLow = (tempOffset & 0xFFFFFFFF);

		char *buffer = new char[bufferSize + tempBufferSize];

		for(int i = 0; i < tempBufferSize; i++)
		{
			buffer[i] = tempBuffer[i];
		}

		//creating file mapping
		HANDLE inputFile = (HANDLE)OpenFile(inputFileName, &tOfStr, NULL);
		if (!inputFile)
		{
			logger.Fatal("Failed opening input file");
			exit(0);
		}
		HANDLE fileMap = CreateFileMapping(inputFile, NULL, PAGE_READONLY, 0, 0, NULL);
		if (!fileMap)
		{
			logger.Fatal("Failed input file mapping");
			exit(0);
		}
		char *tmp_buffer = (char *)MapViewOfFile(fileMap, FILE_MAP_READ, (int)offsetHigh, (int)offsetLow, bufferSize + offset - tempOffset);

		//writing memory mapped file to buffer with needed offset
		memcpy(&buffer[tempBufferSize], &tmp_buffer[offset - tempOffset], bufferSize);

		offset += bufferSize;
		tempOffset = (offset / granularity) * granularity;

		offsetHigh = ((tempOffset >> 32) & 0xFFFFFFFF);
		offsetLow = (tempOffset & 0xFFFFFFFF);

		//checking if the next character is number (that means we have cutted some numbers)
		if (offset < fileSize)
		{
			char *next;
			next = (char *)MapViewOfFile(fileMap, FILE_MAP_READ, (int)offsetHigh, (int)offsetLow, offset - tempOffset + 1);
			char nextCh = next[offset - tempOffset];

			if (nextCh >= '0' && nextCh <= '9')
			{
				cutted = true;
			}

			UnmapViewOfFile(next);
		}

		VirtualUnlock(tmp_buffer, bufferSize);
		UnmapViewOfFile(tmp_buffer);

		CloseHandle(fileMap);
		CloseHandle(inputFile);

		//processing created chunk
		ProcessChunk(buffer, cutted, bufferSize, index);

		index++;
	}
	logger.Debug("Splitting finished");
}

//loading queues
void LoadQueues(queue<unsigned int> *queues, int index)
{
	long long queueBufferSize;
	//checking if it is the end of file
	if (offsets[index] == fileSizes[index] + 1)
		return;
	//getting needed buffer size
	if (positions[index].empty())
		queueBufferSize = fileSizes[index] - offsets[index];
	else
	{
		queueBufferSize = positions[index].back() - offsets[index];
		positions[index].pop_back();
	}

	long long tempOffset = (offsets[index] / granularity) * granularity;

	long long offsetHigh = ((tempOffset >> 32) & 0xFFFFFFFF);
	long long offsetLow = (tempOffset & 0xFFFFFFFF);

	OFSTRUCT tOfStr;
	tOfStr.cBytes = sizeof tOfStr;

	//mapping buffer to memory
	HANDLE inputFile = (HANDLE)OpenFile(fileNames[index], &tOfStr, OF_READ); 
	HANDLE fileMap = CreateFileMapping(inputFile, NULL, PAGE_READONLY, 0, 0, NULL);

	//int n = offsets[index] - tempOffset;

	char *tmp_buffer = (char *)MapViewOfFile(fileMap, 
		FILE_MAP_READ, 
		(int)offsetHigh, 
		(int)offsetLow,
		queueBufferSize + offsets[index] - tempOffset);
	char *buffer = new char[queueBufferSize];
	memcpy(&buffer[0], &tmp_buffer[offsets[index] - tempOffset], queueBufferSize);

	//pushing numbers to queue
	int num = 0;
	for (int i = 0; i < queueBufferSize; i++)
	{
		if (buffer[i] != ' ')
		{
			num *= 10;
			num += buffer[i] - '0';
		}
		else
		{
			queues[index].push(num);
			num = 0;
		}
	}
	queues[index].push(num);

	UnmapViewOfFile(tmp_buffer);
	CloseHandle(inputFile);
	CloseHandle(fileMap);
	free(buffer);
	offsets[index] += queueBufferSize + 1;
}

//merging chunks function
void MergeChunks(string outputFileName)
{
	logger.Debug("Merging started");
	
	HANDLE output = CreateFile(outputFileName.c_str(), 
		GENERIC_WRITE, 
		FILE_SHARE_WRITE, 
		NULL, 
		CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL, 
		NULL);

	if (!output)
	{
		logger.Fatal("Failed creating output file");
		exit(0);
	}

	unsigned int lowestValue;
	int lowestIndex;

	//loading queues
	queue<unsigned int> *queues = new queue<unsigned int>[chunksNum];
	for (int i = 0; i < chunksNum; i++)
	{
		LoadQueues(queues, i);
	}

	int bufSize = 0;
	char *outputBuffer = new char[330000010];
	int position = 0;
	while (totalCount > 0)
	{
		lowestIndex = -1;
		lowestValue = 0;

		//getting lowest value and index of file where it is
		for (int i = 0; i < chunksNum; i++)
		{
			if (!queues[i].empty())
			{
				if (lowestIndex < 0 || queues[i].front() <= lowestValue)
				{
					lowestIndex = i;
					lowestValue = queues[i].front();
				}
			}
		}

		//writing lowest value to buffer
		char *temp = new char[10];
		sprintf(temp, "%u", lowestValue);
		int length = strlen(temp);
		for (int i = 0; i < length; i++)
		{
			outputBuffer[position + i] = temp[i];
		}
		free(temp);
		position += length;

		bufSize++;

		if (--totalCount > 0)
		{
			outputBuffer[position] = ' ';
			position++;
		}

		//if buffer is filled - writing it to the file
		if (bufSize == 30000001 || totalCount == 0)
		{
			DWORD writtenBytes;
			bool written = WriteFile(output, outputBuffer, position, &writtenBytes, 0);
			if (!written)
			{
				logger.Fatal("Writing to output file failed");
				exit(0);
			}
			bufSize = 0;
			position = 0;
			free(outputBuffer);
			outputBuffer = new char[330000010];
		}

		queues[lowestIndex].pop();

		//if queue is empty loading it
		if (queues[lowestIndex].size() == 0)
		{
			LoadQueues(queues, lowestIndex);
		}
	}

	free(outputBuffer);
	for (int i = 0; i < chunksNum; i++)
		DeleteFile(fileNames[i]);
	RemoveDirectory(tempPath);
	CloseHandle(output);
	logger.Info("Merging finished");
}

void main(int argc, char *argv[])
{
	time_t start_time;
	time(&start_time);
	Initialize(argc, argv);
	logger.Info("Sorting started");
	Split(inputFileName); //splitting file
	for (int i = 0; i < chunksNum; i++)
		offsets[i] = 0;
	MergeChunks(outputFileName); //merging chunks
	time_t end_time;
	time(&end_time);
	time_t duration = end_time - start_time;
	Deinitialize();
	logger.Info("Sorting finished");
	logger.Info("Time estimated: %d", duration);
}